import utilClass.TreeNode;

public class RouteSum {


    public static int sum(TreeNode node,int n){
        if(node==null){
            return 0;
        }
        int ret=getRootSum(node,n);
        ret+=sum(node.right,n);
        ret+=sum(node.left,n);
        return ret;
    }



    public static int getRootSum(TreeNode node,int n){
        if(node==null){
            return 0;
        }

        int ret=0;
        if(node.val==n){
            ret++;
        }
        ret+=getRootSum(node.left,n-node.val);
        ret+=getRootSum(node.right,n-node.val);
        return ret;
    }
}
